package DataStructure.graph;

import java.util.ArrayDeque;
import java.util.Deque;

//有向无权图
public class DGraph {
    private int V;//顶点数量
    private int E;//边数量
    private Deque<Edge> edge;//边
    private int[] in;//入度
    private int[] out;//出度
    private Deque<Integer>[] adj;//邻接表

    private boolean[] mark;//访问标志
    private boolean[] on;//本次路径上的节点
    private Deque<Integer> s;//结果栈


    public DGraph(int v) {
        V = v;
        E = 0;
        edge=new ArrayDeque<>();
        in=new int[v];
        out=new int[v];
        adj = new ArrayDeque[v];
        for (int i = 0; i < adj.length; i++) {
            adj[i]=new ArrayDeque<>();
        }
        mark=new boolean[v];
        on=new boolean[v];
        s=new ArrayDeque<>();
    }

    //fix
    public Deque<Integer> near(int v){
        return adj[v];
    }

    public void addEdge(int v,int w){
        if(adj[v].contains(w))
            return;
        edge.add(new Edge(v,w));
        out[v]++;
        in[w]++;
        adj[v].add(w);
        E++;
    }

    //拓扑排序 test
    //递归
    public Deque<Integer> topoSort(){
        //从每个顶点开始，如果已经搜索则跳过
        for (int i = 0; i < V; i++) {
            if (!mark[i]) {
                if(!dfs(i)) return null;//有环返回空
            }
        }
        return s;
    }
    private boolean dfs(int v){
        mark[v]=true;
        on[v]=true;
        for (int w : adj[v]) {
            if(!mark[w]){
                if(!dfs(w))
                    return false;
            } else if(on[w]){//已经标记的点，可能是之前遍历过的，也可能是本次路径上的
                return false;
            }
        }
        on[v]=false;//回溯还原路径上点的状态
        s.add(v);//当该点没有指向，或已经遍历完后面的点，该点入栈
        return true;
    }

    //非递归
    public Deque<Integer> topoSort2(){
        Deque<Integer> q=new ArrayDeque<>();
        //将入度为0的顶点加入队列
        for (int i = 0; i < V; i++) {
            if(in[i]==0)
                q.add(i);
        }
        while(!q.isEmpty()){
            int v=q.poll();//取出入度为0的顶点
            s.addFirst(v);
            for (int w:adj[v]) {
                in[w]--;//v指向的顶点入度减1
                if(in[w]==0)
                    q.add(w);
            }
        }
        if(s.size()<V)//存在环,环节点的入度至少为1
            return null;
        return s;
    }


}
